#!/usr/bin/python
from pylab import *
# from matplotlib.collections import PatchCollection
# import matplotlib.patches as mpatches
# import matplotlib.lines as mlines
from matplotlib.patches import FancyBboxPatch
from matplotlib.patches import Wedge
import copy

# # font = "sans-serif"
# fig = figure(figsize=(10,10))
# #l# ax = fig.add_axes([0,0,1,1])  # the ticks not displayed
# ax = fig.add_axes([0.1,0.1,0.8,0.8])
# # ax = fig.add_subplot(111)

# fig, ax = plt.subplots()


# # # create 3x3 grid to plot the artists
# # # pos = np.mgrid[0.2:0.8:3j, 0.2:0.8:3j].reshape(2, -1)


# # # ax.add_line(line)               # add lines
# xlim(0,300)                       # must set the xlim/ylim manually
# ylim(0,300)
# # # ax.set_xticks([])
# # # ax.set_yticks([])
# # ax.set_xticks([-1, -0.5, 0, 0.5, 1], ['$-\pi$', '$-\pi/2$', '$0$', '$+\pi/2$', '$+\pi$'])
   


# ==================== func for plot ====================
# global parameters
step_x = 10                     # the diameter of a node in the grid
step_y = 10

def new_fig(title=None):
   global fig, ax, plot_base_pos
   fig, ax = subplots()
   if title != None:
      fig.suptitle(title)
   fig.set_facecolor("white")
   fig.set_dpi(72)
   fig.set_size_inches(16.0, 5.0)
   ax.set_xlim(0,350)
   ax.set_ylim(0,140)
   ax.set_frame_on(False)
   ax.get_xaxis().set_visible(False)
   ax.get_yaxis().set_visible(False)
   plot_base_pos = (0,1)
   return (fig, ax)

def plot_circle(center, radius, **kwargs):
   patch = Circle(center, radius, **kwargs)
   ax.add_patch(patch)

def plot_half_circle(center, radius, theta1, theta2, **kwargs):
   patch = Wedge(center, radius, theta1, theta2, **kwargs)
   ax.add_patch(patch)

def plot_yinyang_circle(center, radius, color1, color2, **kwargs):
   ax.add_patch(Wedge(center, radius, 90, 270, color=color1))
   ax.add_patch(Wedge(center, radius, -90, 90, color=color2))

# def plot_concentric_circle(center, radius, **kwargs):
   
def plot_dot(pos, **kwargs):
   radius = 2
   linewidth = 1.5
   color = "black"
   fill = "True"

   if "color" in kwargs:
      color = kwargs['color']
   if "fill" in kwargs:
      fill = kwargs['fill']

   dotstyle = "solid_circle"
   if "dotstyle" in kwargs:
      dotstyle = kwargs["dotstyle"]

   # if  style == "solid_circle":
   #    plot_circle(pos, radius, color=color, fill=fill)
   if dotstyle == "half_circle":
      plot_half_circle(pos, radius, theta1=90, theta2=270, color=color, fill=fill)
   elif dotstyle == "concentric_circle":
      plot_circle(pos, radius, fill=True, linewidth=3, fc=kwargs['colors'][0], ec=kwargs['colors'][1])
   elif dotstyle == "yinyang_circle":
      plot_yinyang_circle(pos, radius, color1=kwargs['colors'][0], color2=kwargs['colors'][1], fill=fill)
   else:
      plot_circle(pos, radius, color=color, fill=fill, linewidth=linewidth)
   
def plot_rect(start_pos, end_pos, **kwargs):
   # start_pos and end_pos is any pair of the diagonal point
   if start_pos[0] < end_pos[0]:
      sx = start_pos[0]
      ex = end_pos[0]
   else:
      sx = end_pos[0]
      ex = start_pos[0]

   if start_pos[1] < end_pos[1]:
      sy = start_pos[1]
      ey = end_pos[1]
   else:
      sy = end_pos[1]
      ey = start_pos[1]

   width = ex - sx + 1
   height = ey - sy + 1
   
   # sx = start_pos[0] if start_pos[0]<end_pos[0] else end_pos[0]
   # sy = start_pos[1] if start_pos[1]<end_pos[1] else end_pos[1]
   patch = Rectangle((sx, sy), width, height, **kwargs)
   ax.add_patch(patch)

# style : None:the original style(controlled by dots[x][x][1]); 
#         text:display all dots' value;
#         dot :display all dots as a dot (e.g, solid circle)
def display_dots(dots, base_pos=None, plot_ax=None, style=None, **kwargs):
   global ax, plot_base_pos
   if plot_ax != None:
      ax = plot_ax
   if base_pos != None:
      plot_base_pos = base_pos
   base_point = (plot_base_pos[0]+step_x/2, plot_base_pos[1]+step_y/2)
   # add one row for display ticks
   disp_rows_num = grid_rows_num + 1
   # ticks = [(str(i),True) for i in range(grid_cols_num)]
   # disp_dots = [ticks] + dots
   # for y in range(disp_rows_num):
   #    for x in range(grid_cols_num):
   #       pos = (base_point[0]+step_x*(cols_num-1-x), base_point[1]+step_y*(disp_rows_num-1-y))
   #       assert(type(disp_dots[y][x]) == tuple)
   #       if disp_dots[y][x][0] == 0: # empty cell, do nothing, ignore the isDispText field
   #          continue
   #       elif (style=="dot" and y!=0) or (style!="text" and disp_dots[y][x][1]==False): # row 0 must display as text (it's ticks)
   #          plot_dot(pos, **kwargs)
   #       else:
   #          text(pos[0], pos[1], disp_dots[y][x][0], ha="center", va="center", family="sans-serif", size=10, **kwargs)


   for x in range(grid_cols_num):
      pos = (base_point[0]+step_x*(grid_cols_num-1-x), base_point[1]+step_y*(disp_rows_num-1))
      text(pos[0], pos[1], str(x), ha="center", va="center", family="sans-serif", size=10)

   for y in range(grid_rows_num):
      for x in range(grid_cols_num):
         pos = (base_point[0]+step_x*(grid_cols_num-1-x), base_point[1]+step_y*(disp_rows_num-1-y-1))
         assert(type(dots[y][x]) == tuple)
         if dots[y][x][0] == 0: # empty cell, do nothing, ignore the isDispText field
            continue
         elif style=="dot" or (style!="text" and dots[y][x][1]==False):
            plot_dot(pos, **kwargs)
         else:
            kwargs.pop('fill', None)
            text(pos[0], pos[1], dots[y][x][0], ha="center", va="center", family="sans-serif", size=10, **kwargs)

   # draw the grid
   pos_left_buttom = (plot_base_pos[0], plot_base_pos[1])
   pos_right_top = (plot_base_pos[0]+step_x*grid_cols_num, plot_base_pos[1]+step_y*disp_rows_num)
   # the boundaries
   plot_rect(pos_left_buttom, pos_right_top, fill=False, color="black")
   # the table header
   tab_header_start_pos = (pos_left_buttom[0], pos_right_top[1]-step_y)
   tab_header_end_pos = pos_right_top
   plot_rect(tab_header_start_pos, tab_header_end_pos, fill=True, color='red', alpha=0.8)
   # the columns
   # lineX = [plot_base_pos[0]+step_x*i for i in range(1,cols_num)]
   for i in range(1,grid_cols_num):
      x = plot_base_pos[0]+step_x*i
      y0 = pos_left_buttom[1]
      y1 = pos_right_top[1]
      line = Line2D([x,x], [y0, y1], lw=1, c='black')
      ax.add_line(line)
   # the rows
   for i in range(1, disp_rows_num):
      y = plot_base_pos[1]+step_y*i
      x0 = pos_left_buttom[0]
      x1 = pos_right_top[0]
      line = Line2D([x0,x1], [y,y], lw=1, c='black')
      ax.add_line(line)


# draw oval vertical
def plot_oval(start_pos, end_pos, **kwargs):
   # patch = mpatches.FancyBboxPatch((pos[0]-step_x/2,pos[1]-step_y/2), step_x, 30, fill=False, color="blue", linewidth=3, boxstyle=mpatches.BoxStyle("Round", pad=0))
   if start_pos[0] < end_pos[0]:
      sx = start_pos[0]
      ex = end_pos[0]
   else:
      sx = end_pos[0]
      ex = start_pos[0]

   if start_pos[1] < end_pos[1]:
      sy = start_pos[1]
      ey = end_pos[1]
   else:
      sy = end_pos[1]
      ey = start_pos[1]

   width = ex - sx + 1
   height = ey - sy + 1

   patch = FancyBboxPatch((sx, sy), width, height, linewidth=2, boxstyle="Round, pad=3", **kwargs)
   ax.add_patch(patch)


def dot2pos(row, col, plot_base_pos):
   disp_rows_num = grid_rows_num + 1
   base_point = (plot_base_pos[0]+step_x/2, plot_base_pos[1]+step_y/2)
   pos = (base_point[0]+step_x*(grid_cols_num-1-col), base_point[1]+step_y*(disp_rows_num-1-(row+1)))
   return pos
 

def mark_dots(start_dot, end_dot=None, base_pos=None, color="red"):
   global plot_base_pos
   if end_dot == None:
      end_dot = start_dot
   if base_pos != None:
      plot_base_pos = base_pos
   spos, epos = dot2pos(start_dot[0], start_dot[1], plot_base_pos), dot2pos(end_dot[0], end_dot[1], plot_base_pos)
   plot_oval(spos, epos, color=color, fill=False)


def display_compress_groups(compress_groups, base_pos=None):
   global plot_base_pos
   if base_pos != None:
      plot_base_pos = base_pos
   # draw the select oval
   for col in range(grid_cols_num):
      cnt = 0
      for n in compress_groups[col]:
         if n==2 or n==3:
            mark_dots(start_dot=(cnt,col), end_dot=(cnt+n-1,col), base_pos=plot_base_pos, color="red")
            # spos, epos = dot2pos(cnt, col, plot_base_pos), dot2pos(cnt+n-1, col, plot_base_pos)
            # plot_oval(spos, epos, color="red", fill=False)
         cnt += n

# ========== func for PP generate, compress and other process ==========
# width = 16                               # width x width multiply
# col_middle = width
# pps_num = width/2+1                      # num of pps
# pps_width = width + 1                    # the width of last PP is width
# cols_num = width*2
# rows_num = width/2+1

def dots_grid_init(rows, cols=None):
   # global width, col_middle, pps_num, pps_width, cols_num, rows_num
   global grid_rows_num, grid_cols_num
   grid_rows_num = rows
   grid_cols_num = cols if cols!=None else rows

   # mcand_width = cols_num
   # mcand_col_middle = mcand_width
   # pps_num = width/2+1                      # num of pps
   # pps_width = width + 1                    # the width of last PP is width

# def gen_empty_dots_array(rows, cols):
#    # return [[0]*cols for i in range(rows)]
#    return [[(0,False)]*cols for i in range(rows)] # for each unit, two values : (val, isDispText)

def gen_empty_dots_array(rows=None, cols=None, dot_default=(0,False)):
   if rows == None and cols == None:
      rows, cols = grid_rows_num, grid_cols_num
   assert (rows != None and cols != None)
   # return [[(0,False)]*cols for i in range(rows)] # for each unit, two values : (val, isDispText)
   return [[dot_default]*cols for i in range(rows)] # for each unit, two values : (val, isDispText)
   
# pp0_height_reduction should change only for counteracting or demo in few scheme
# pp_index_start only used for special scheme
def gen_pp(mcand_width, mplier_width, prefix="", pp_index_start=(0,0), pp0_height_reduction=True, prod_negate=False):
   assert(mplier_width%2 == 0)   # the length of mplier must be an even num

   pps_width = mcand_width + 1
   mplier_ext_width = mplier_width + 2 + 1
   pps_num = mplier_width/2+1
   
   dots = gen_empty_dots_array()
   
   for row in range(pps_num):
      pp_width = pps_width if row<pps_num-1 else pps_width-1      # the last row, one less than others
      for i in range(pp_width):
         dots[row][row*2+i] = ("%spp[%d][%d]" % (prefix, pp_index_start[0]+row, pp_index_start[1]+i), False)
      if row < pps_num-1:
         dots[row+1][row*2] = ("%sS[%d]" % (prefix, pp_index_start[0]+row), True)
      if row>=1 and row<=pps_num-2:
         dots[row][row*2+pps_width] = ("%sE[%d]" % (prefix, pp_index_start[0]+row), True)
      if row>=1 and row<=pps_num-3:
         dots[row][row*2+pps_width+1] = ("1'b1", True)
   dots[0][pps_width] = ("{~%sE[%d]}" % (prefix, pp_index_start[0]+0), True) # for the first row
   dots[0][pps_width+1] = ("{~%sE[%d]}" % (prefix,pp_index_start[0]+0), True)
   dots[0][pps_width+2] = ("%sE[%d]" % (prefix,pp_index_start[0]+0), True)

   # only when the last pp need negated(to calc -A*B)
   if prod_negate == True:
      assert(pps_num+1<=grid_rows_num)
      dots[pps_num][(pps_num-1)*2] = ("%sS[%d]" % (prefix, pp_index_start[0]+pps_num-1), True)
   
   # only for counteracting or demo in few scheme
   if pp0_height_reduction == False:
      assert(grid_rows_num >= pps_num+1)     # must ensure rows_num is large enough (rows_num >= pps_num+1)
      for row in range(grid_rows_num-1, 0, -1):
         for col in range(grid_cols_num):
            dots[row][col] = dots[row-1][col];
      for col in range(grid_cols_num):
         dots[0][col] = (0,False)
      dots[0][pps_width] = ("1'b1", True)
      dots[1][pps_width] = ("%sE[%d]" % (prefix, pp_index_start[0]+0), True)
      dots[1][pps_width+1] = ("1'b1", True)
      dots[1][pps_width+2] = (0, False)
   return dots


# def set_dots_cell(dots, pos, val):
#    row, col = pos
#    dots[row][col] = val

def set_dots_cell(dots, (row,col), val):
   dots[row][col] = val

def set_dots_col(dots, col, col_val_list):
   for row, val in enumerate(col_val_list): 
      dots[row][col] = val

# notice : this func only set value but never clear any cells, so you may need input an empty dots as 'dots' param
def set_pp(dots, row, pp_val, start_col=None, s_val=None):
   if start_col == None:
      start_col = row*2
   for col,val in enumerate(pp_val):
      dots[row][start_col+col] = val
   # for i in range(start_col):
   #    dots[row][i] = (0, False)
   # for i in range(start_col+len(pp_val), cols_num):
   #    dots[row][i] = (0, False)
   if s_val != None:
      assert(type(s_val) == tuple)
      dots[row+1][start_col] = s_val

def shift_left(dots, n):
   for col in range(grid_cols_num-1,n-1,-1):
      for row in range(grid_rows_num):
         dots[row][col] = dots[row][col-n]
   for col in range(n):
      for row in range(grid_rows_num):
         dots[row][col] = (0, False)

# reorganize upwards the dots
def reorg_upward(dots):
   dots_up = gen_empty_dots_array()
   for col in range(grid_cols_num):
      items = []
      for row in range(grid_rows_num):
         if dots[row][col][0] != 0:
            items.append(dots[row][col])
      # items += [None]*(rows_num - len(items))
      for row, val in enumerate(items):
         dots_up[row][col] = val
   return dots_up

def get_col_items(dots):
   cols = []
   for col in range(grid_cols_num):
      items = []
      for row in range(grid_rows_num):
         val = dots[row][col][0]
         if val != 0:
            items.append(val)
      # if items == []:
      #    items = ["0"]
      cols.append(items)
   return cols

def get_row_items(dots):
   rows = []
   for row in range(grid_rows_num):
      items = []
      for col in range(grid_cols_num-1,-1,-1): # here should traverse reversely
         val = dots[row][col][0]
         if val == 0:
            items.append("1'b0")
         else:
            items.append(val)
      rows.append(items)
   return rows

def print_col_formula(dots, prefix="col"):
   cols = get_col_items(dots)
   for col,items in enumerate(cols):
      if items == []:
         items = ["0"]
      print "%s[%d] = %s;" % (prefix, col, ' + '.join(items))

def print_row_formula(dots, prefix="row"):
   rows = get_row_items(dots)
   for row,items in enumerate(rows):
      reduce_items = []
      zero_cnt = 0
      for i in items:
         if i == "1'b0":
            zero_cnt += 1
         else:
            if zero_cnt != 0:
               reduce_items.append("%d'b0" % zero_cnt)
               zero_cnt = 0
            reduce_items.append(i)
      if zero_cnt != 0:
         reduce_items.append("%d'b0" % zero_cnt)

      print "%s[%d] = {%s};" % (prefix, row, ' , '.join(reduce_items))

# def print_row_formula(dots):
#    rows = get_row_items(dots)
#    for row, items in enumerate(rows):
#       print "row[%d] = {%s};" % (row, ' , '.join(items))

# for traversing all dots
def all_dots(dots):
   for row in range(grid_rows_num):
      for col in range(grid_cols_num):
         yield dots[row][col]

# traverse all valid dots (ignore the empty one)
def traverse_dots(dots, process_func):
   for row in range(grid_rows_num):
      for col in range(grid_cols_num):
         if dots[row][col][0] != 0:
            new_value = process_func(dots[row][col][0])
            if new_value != None:
               dots[row][col] = (new_value, dots[row][col][1])



def wallace_init(dots):
   global compress_array, compress_stage, compress_dots
   compress_array = []
   compress_stage = len(compress_array) - 1
   compress_dots = dots

   
def is_compress_finish():
   global compress_dots
   for col in range(grid_cols_num):
      cnt = 0
      for row in range(grid_rows_num):
         if compress_dots[row][col][0] != 0:
            cnt += 1
         else:
            break
      if cnt > 2:
         return False
   return True

# the dots must already reorganized upwards as an inverted triangle
def wallace_compress():
   global compress_array, compress_stage, compress_dots

   compress_array.append([[] for i in range(grid_cols_num)])
   compress_stage = len(compress_array) - 1

   cols_carry = [[] for i in range(grid_cols_num)] # the carry of all columns
   compress_groups = []         # the groups to compress for all columns (the return value)
   
   for col in range(grid_cols_num):
      items = []
      for row in range(grid_rows_num):
         if compress_dots[row][col][0] == 0: # FIXME: but if there not exist any dots ?
            break               # finish
         else:
            items.append(compress_dots[row][col][0])
      n_compress_3_2 = len(items) / 3
      n_reminder = len(items) % 3
      
      curr_col_result = []
      fields = []
      # clac current col's sum
      i = -1
      for i in range(n_compress_3_2):
         comp_in = items[i*3:(i+1)*3]       # from i*3 to i*3+2
         comp_sum = "S%d_%d_%d" % (compress_stage+1, col, i) # stage_col_row
         # comp_carry = "S%d_%d_Carry_%d" % (compress_stage+1, col+1, i)  # this is not the real name which is determined by next col
         comp_carry = "S%d_%d_Carry_%d" % (compress_stage+1, col, i)  # this is not the real name which is determined by next col
         compress_io = [comp_carry, comp_sum] + comp_in # (3,2) counter / full adder
         
         curr_col_result.append(comp_sum)
         cols_carry[col].append(comp_carry)
         compress_array[compress_stage][col].append(compress_io)

         fields.append(3)
      
      
      if n_reminder == 2:
         i += 1
         comp_in = items[i*3:]
         assert(len(comp_in) == 2)
         comp_sum = "S%d_%d_%d" % (compress_stage+1, col, i)
         # comp_carry = "S%d_%d_Carry_%d" % (compress_stage+1, col+1, i)
         comp_carry = "S%d_%d_Carry_%d" % (compress_stage+1, col, i)
         compress_io = [comp_carry, comp_sum] + comp_in # (2,2) counter/half adder

         curr_col_result.append(comp_sum)
         cols_carry[col].append(comp_carry)
         compress_array[compress_stage][col].append(compress_io)

         fields.append(2)

      elif n_reminder == 1:
         i += 1
         comp_in = items[i*3]
         comp_sum = "S%d_%d_%d" % (compress_stage+1, col, i) 
         compress_io = [comp_sum, comp_in]              # just a wire
         
         curr_col_result.append(comp_sum)
         compress_array[compress_stage][col].append(compress_io)
      
         fields.append(1)

      compress_groups.append(fields)

      # calc the previous col's carry out (get its real name)
      if col >= 1:              # ignore column 0, there is no carry
         for j in range(len(cols_carry[col-1])):
            prev_carry = "S%d_%d_%d" % (compress_stage+1, col, i+j+1)
            curr_col_result.append(prev_carry)
            cols_carry[col-1][j] = prev_carry # rename to the real name
            compress_array[compress_stage][col-1][j][0] = prev_carry # rename the previous col's carry out 

      # record the compress result
      for row,v in enumerate(curr_col_result):
         compress_dots[row][col] = (v,False)
      for r in range(row+1, grid_rows_num, 1):
         compress_dots[r][col] = (0,False)

   return compress_groups

def print_compress_sverilog_code():
   stage_num = len(compress_array)
   compress_operations = [[] for i in range(stage_num)]
   create_wires = [[] for i in range(stage_num)]
   FA_cnt = 1
   HA_cnt = 1
   for stage in range(stage_num):
      for col in range(grid_cols_num):
         for item in compress_array[stage][col]:
            # tmp_str = ""
            # for i in item:
            #    if i == '1':        # replace "1" width "1'b1"
            #       tmp_str += "1'b1,"
            #    else:
            #       tmp_str += i+","
            # tmp_str = tmp_str[:-1]
            tmp_str = ','.join(item)
            if len(item) == 5:     # full adder
               compress_operations[stage].append("FA fa%d (%s);" % (FA_cnt, tmp_str))
               create_wires[stage] += item[0:1]
               FA_cnt += 1
            elif len(item) == 4:   # half adder
               compress_operations[stage].append("HA ha%d (%s);" % (HA_cnt, tmp_str))
               create_wires[stage] += item[0:1]
               HA_cnt += 1
            elif len(item) == 2:   # just wire
               # compress_operations[stage].append("assign %s = %s;" % (item[0], tmp_str))
               compress_operations[stage].append("assign %s;" % (tmp_str.replace(",", " = ")))
               create_wires[stage] += [item[0]]
            else:
               assert(False)

   wires_str = ""
   print "// ==================== wires need create ===================="
   for stage in range(stage_num):
      wires_str += "logic " + ','.join(create_wires[stage]) + ";\n"
   # print wires_str

   # compress_str = ""
   compress_str = wires_str
   # compress_str += "logic [%d:0] final_pp0, final_pp1;" % (grid_cols_num-1)
   for stage in range(stage_num):
      compress_str += "// ==================== Stage%d ====================\n" % (stage+1)
      for op in compress_operations[stage]:
         compress_str += op + '\n'
   # the final 2 PPs
   final_pp0 = ""
   final_pp1 = ""
   for col in range(grid_cols_num-1,-1,-1):
      assert(compress_dots[0][col][0]!=0)
      final_pp0 += compress_dots[0][col][0] + ',' # the items of row 0 never has a '0'
      if compress_dots[1][col][0] == 0:
         final_pp1 += "1'b0,"
      else:
         final_pp1 += compress_dots[1][col][0] + ','
   final_pp0 = "{" + final_pp0[:-1] + "}"
   final_pp1 = "{" + final_pp1[:-1] + "}"
   compress_str += "// ==================== Final 2 PPs ====================\n"
   compress_str += "assign final_pp0 = %s;\n" % final_pp0
   compress_str += "assign final_pp1 = %s;\n" % final_pp1
   print compress_str
   print "// -------------------- total %d FAs and %d HAs --------------------" % (FA_cnt-1, HA_cnt-1)
   #   return (FA_cnt-1, HA_cnt-1)





# mix the two dots with the condition: cond_1 ? dots1 : dots2
def mix_dots(dots1, dots2, cond_1, sort_cols=True):
   dots_distribute_cnt = []

   cols_1 = get_col_items(dots1)
   cols_2 = get_col_items(dots2)
   if sort_cols == True:
      for items in cols_1:
         items.sort(reverse=True)
      for items in cols_2:
         items.sort(reverse=True)
   cols_mix = []
   for col in range(grid_cols_num):
      col_common = []
      col_1_only = []
      col_2_only = []
      for i in cols_1[col]:
         if i in cols_2[col]:
            cols_2[col].remove(i)
            col_common.append(i)
         else:
            col_1_only.append(i)
      col_2_only = cols_2[col]

      dots_distribute_cnt.append((len(col_common), len(col_1_only), len(col_2_only)))
      # construct the new column by the cond_1
      alternate_len = min(len(col_1_only), len(col_2_only))
      for i in range(alternate_len):
         d1 = col_1_only.pop(0)
         d2 = col_2_only.pop(0)
         col_common.append("(%s ? %s : %s)" % (cond_1, d1, d2))
      for d1 in col_1_only:
         # col_common.append("(%s & %s)" % (cond_1, d1))
         if d1 == "1'b1":
            col_common.append(cond_1)
         else:
            col_common.append("(%s & %s)" % (cond_1, d1))
      for d2 in col_2_only:
         # col_common.append("(~%s & %s)" % (cond_1, d2))
         if d2 == "1'b1":
            col_common.append("{~%s}" % cond_1)
         else:
            col_common.append("(~%s & %s)" % (cond_1, d2))
         
      cols_mix.append(col_common)

   dots_mix = gen_empty_dots_array()
   for col, items in enumerate(cols_mix):
      val_list = [(i,False) for i in items]
      set_dots_col(dots_mix, col, val_list)


   # generate the dots distribute statistics
   dots_distribute = gen_empty_dots_array(dot_default=(0,()))
   for col in range(grid_cols_num):
      common, only_1, only_2 = dots_distribute_cnt[col]
      base_row = 0
      for row in range(common):
         # dots_distribute[base_row+row][col] = ("concentric_circle", ("red", "black"))
         dots_distribute[base_row+row][col] = ("solid_circle", ("blue"))
      base_row += common
      for row in range(min(only_1, only_2)):
         dots_distribute[base_row+row][col] = ("yinyang_circle", ("red", "black"))
      base_row += min(only_1, only_2)
      color = "red" if only_1 > only_2 else "black"
      for row in range(abs(only_1-only_2)):
         dots_distribute[base_row+row][col] = ("solid_circle", (color))
   
   #return dots_mix
   return dots_mix, dots_distribute

def set_switch(dots, switch):
   dots_switched = gen_empty_dots_array()
   for row in range(grid_rows_num):
      for col in range(grid_cols_num):
         if dots[row][col][0] == 0:
            continue
         elif dots[row][col][0] == "1'b1":
            dots_switched[row][col] = (switch, dots[row][col][1])
         else:
            dots_switched[row][col] = ("(%s & %s)" % (switch, dots[row][col][0]), dots[row][col][1])
   return dots_switched


def get_dots_actual_area(dots):
   row_min, row_max, col_min, col_max = grid_rows_num-1, 0, grid_cols_num-1, 0
   for row in range(grid_rows_num):
      for col in range(grid_cols_num):
         if dots[row][col][0] != 0:
            row_min = row if row<row_min else row_min
            row_max = row if row>row_max else row_max
            col_min = col if col<col_min else col_min
            col_max = col if col>col_max else col_max
   
   assert row_min <= row_max and col_min <= col_max # otherwise the dots is empty 
   return (row_min, col_min, row_max, col_max)

# def get_dots_actual_size(dots):
#    area = get_dots_actual_area(dots)

# get the start row of empty area for the specific cols   
def get_empty_row_spec_cols(dots, start_col, end_col):
   for row in range(grid_rows_num-1,-1,-1):
      for col in range(start_col, end_col+1):
         if dots[row][col][0] != 0:
            if row == grid_rows_num-1: # no empty area
               return None
            else:
               return row+1
   return 0
   
   
def add_to_dots(dots, dots_sum):
   row_min, col_min, row_max, col_max = get_dots_actual_area(dots)
   start_row = get_empty_row_spec_cols(dots_sum, col_min, col_max)
   assert start_row+(row_max-row_min+1) -1 <= grid_rows_num-1
   for row in range(row_min, row_max+1):
      for col in range(col_min, col_max+1):
         dots_sum[start_row + (row-row_min)][col] = dots[row][col]

def add_dots(*alldots):
   dots_sum = gen_empty_dots_array()
   for dots in alldots:
      add_to_dots(dots, dots_sum)
   return dots_sum


def copy_cut_dots(dots, start_dot, end_dot, need_clear):
   row_min = min(start_dot[0], end_dot[0])
   row_max = max(start_dot[0], end_dot[0])
   col_min = min(start_dot[1], end_dot[1])
   col_max = max(start_dot[1], end_dot[1])

   dots_rslt = gen_empty_dots_array()
   for row in range(row_min,row_max+1):
      for col in range(col_min,col_max+1):
         dots_rslt[row-row_min][col] = dots[row][col]
         if need_clear == True:
            dots[row][col] = (0,False) # clear the original dot
   return dots_rslt


def cut_dots(dots, start_dot, end_dot):
   return copy_cut_dots(dots, start_dot, end_dot, need_clear=True)

def copy_dots(dots, start_dot, end_dot):
   return copy_cut_dots(dots, start_dot, end_dot, need_clear=False)

   
def display_dots_distribute(dots, base_pos=None, plot_ax=None, style=None, **kwargs):
   global ax, plot_base_pos
   if plot_ax != None:
      ax = plot_ax
   if base_pos != None:
      plot_base_pos = base_pos
   base_point = (plot_base_pos[0]+step_x/2, plot_base_pos[1]+step_y/2)
   # add one row for display ticks
   disp_rows_num = grid_rows_num + 1
   for x in range(grid_cols_num):
      pos = (base_point[0]+step_x*(grid_cols_num-1-x), base_point[1]+step_y*(disp_rows_num-1))
      text(pos[0], pos[1], str(x), ha="center", va="center", family="sans-serif", size=10)

   for y in range(grid_rows_num):
      for x in range(grid_cols_num):
         pos = (base_point[0]+step_x*(grid_cols_num-1-x), base_point[1]+step_y*(disp_rows_num-1-y-1))
         if dots[y][x][0] == 0:
            continue
         else:
            if type(dots[y][x][1]) == tuple:
               plot_dot(pos, dotstyle=dots[y][x][0], colors=dots[y][x][1])
            else:
               plot_dot(pos, dotstyle=dots[y][x][0], color=dots[y][x][1])
   # draw the grid
   pos_left_buttom = (plot_base_pos[0], plot_base_pos[1])
   pos_right_top = (plot_base_pos[0]+step_x*grid_cols_num, plot_base_pos[1]+step_y*disp_rows_num)
   # the boundaries
   plot_rect(pos_left_buttom, pos_right_top, fill=False, color="black")
   # the table header
   tab_header_start_pos = (pos_left_buttom[0], pos_right_top[1]-step_y)
   tab_header_end_pos = pos_right_top
   plot_rect(tab_header_start_pos, tab_header_end_pos, fill=True, color='red', alpha=0.8)
   # the columns
   # lineX = [plot_base_pos[0]+step_x*i for i in range(1,cols_num)]
   for i in range(1,grid_cols_num):
      x = plot_base_pos[0]+step_x*i
      y0 = pos_left_buttom[1]
      y1 = pos_right_top[1]
      line = Line2D([x,x], [y0, y1], lw=1, c='black')
      ax.add_line(line)
   # the rows
   for i in range(1, disp_rows_num):
      y = plot_base_pos[1]+step_y*i
      x0 = pos_left_buttom[0]
      x1 = pos_right_top[0]
      line = Line2D([x0,x1], [y,y], lw=1, c='black')
      ax.add_line(line)
